Search results for "star-free language"

showing 2 items of 2 documents

On the Shuffle of Star-Free Languages

2012

Motivated by the general problem to characterize families of languages closed under shuffle, we investigate some conditions under which the shuffle of two star-free languages is star-free. Some of the special cases here approached give rise to new problems in combinatorics on words.

Discrete mathematicsAlgebra and Number TheorySettore INF/01 - Informaticapure submonoidGeneral problemAbstract family of languagesRegular languageComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Star (graph theory)star-free languageCone (formal languages)shuffle of languagePumping lemma for regular languagesTheoretical Computer ScienceCombinatorics on wordsComputational Theory and MathematicsRegular languagecombinatorics on words.Information SystemsMathematicsFundamenta Informaticae
researchProduct

The Shuffle Product: New Research Directions

2015

In this paper we survey some recent researches concerning the shuffle operation that arise both in Formal Languages and in Combinatorics on Words.

Star-free languageComputer scienceProgramming languageComputer Science (all)Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)computer.software_genreIntermixed languageTheoretical Computer ScienceCombinatorics on wordsTheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITYProduct (mathematics)Formal languageShuffle squarecomputerShuffle
researchProduct